\chapter{Dobrá předuspořádání}

V této kapitole se zaměříme na pojem \emph{dobré předuspořádání}. 
Nejprve zadefinujeme potřebné pojmy a následně si  ukážeme vztah 
dobrých předuspořádí s regulárními jazyky. Ve zbytku kapitoly si popíšeme několik způsobů jak dokázat, že předuspořádání je dobré.


Dobré předuspořádání je reflexivní a tranzitivní relace (předuspořádání),
pro kterou platí, že každá podmnožina obsahuje alespoň jeden minimální prvek a nejvýše 
konečně mnoho takových, které nejsou vzájemně ekvivalentní. 

Jde o zobecnění pojmu \emph{dobrého uspořádání} 
a tento popis se definici dobrého uspořádání nejvíce blíží. Existuje však více zbůsobů jak definovat dobré předuspořádání, z nichž několik uvedeme
 v následující definici. 
 
\begin{definice} 
\label{wqo}
 Předuspořádání $\leq$ na množině $S$ je \emph{dobré předuspořádání} právě tehdy, když platí jedno z následujících:

\begin{enumerate}
  \item[(i)] Každá podmnožina $X \subseteq  S$ obsahuje konečnou podmnožinu $Y\subseteq X$ takovou, 
  že
  \[ \forall x \in X \  \exists y \in Y : y \le x.\]
  \item[(ii)] V libovolné posloupnosti $\{ x_i \}_{i=1}^\infty $ existují $i,j \in \mathbb{N}, i < j$ taková,
   že platí $x_i \leq x_j.$ 
  \item[(iii)] Libovolná nekonečná posloupnost prvků z $S$ obsahuje nekonečnou rostoucí podposloupnost.
  \item[(iv)] Množina $S$ neobsahuje ostře klesající nekonečnou posloupnost ani nekonečnou posloupnost vzájemně neporovnatelných prvků.
  \item[(v)] Libovolná posloupnost uzavřených podmnožin $S$, která je ostře rostoucí vzhledem k inkluzi, je konečná.
\end{enumerate}
\end{definice}

Lze jednoduše ověřit, že všechny čtyři definice jsou ekvivalentní.
První z podmínek se nazývá \emph{vlastnost konečné báze}. Každá uzavřená množina $X$ totiž obsahuje konečnou podmnožinu, jejímž uzávěrem je 
právě množina $X$, která je tak konečně generovaná.Při rozpoznávání jazyků monotónními předuspořádáními nám k regularitě místo konečného indexu stačí vlastnost konečné báze, jak vyplyne z důkazu následující věty.
Důkaz samotný je převzat z ??.


\begin{veta}
\label{genMyh}
Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
monotónnímu dobrému předuspořánaní množiny $\Sigma^*$.
\end{veta}

\begin{proof}


Je jednoduché si uvědomit, že každé předuspořádání konečného indexu je dobré. Stačí nám tedy ukázat, že podmnožiny množiny $\Sigma^*$ uzavřené
vzhledem k monotónnímu dobrému předuspořádání jsou regulární. Důkaz provedeme sporem. Předpokládejme tedy, že máme monotónní dobré předuspořádání $\leq$ na množině
$\Sigma^*$ a množinu $L$ uzavřenou vzhledem k $\leq$, která není regulární. Z věty \ref{Myhill-Nerode} plyne, že relace $\sim_L$ má nekonečný index,
můžeme proto sestrojit nekonečnou posloupnost vzájemně neekvivalentních slov $\{x_i\}_{i=1}^\infty$. Podle definice \ref{wqo} můžeme z posloupnosti $\{x_i\}_{i=1}^\infty$
vybrat rostoucí podposloupnost vzhledem k $\leq$. Můžeme tedy předpokládat, že už samotná posloupnost $\{x_i\}_{i=1}^\infty$ byla vybrána jako rostoucí.
Z monotónie dostáváme, že pro libovolné $y \in \Sigma^*$ a $i < j $ platí $x_i y \leq x_j y$ a z uzavřenosti množiny $X$ plyne, že 
$x_i y \in L \Longrightarrow x_j y \in L $. Proto platí, že posloupnost pravých kontextů $\{C_L^r(x_i)\}_{i=1}^\infty$ je rostoucí vzhledem k inkluzi, a to dokonce ostře, 
neboť slova $x_i$ nejsou vzájemně ekvivalentní. Dále pro libovoná slova $y_1, y_2 \in \Sigma^*$ taková, že $y_1 \leq y_2$, platí $x_i y_1 \in L \Longrightarrow x_i y_2 \in L $.
Jsou tedy množiny $C_L^r(x_i)$  rovněž uzavřené vzhledem k  $\leq$. Posloupnost $\{C_L^r(x_i)\}_{i=1}^\infty$ je tedy nekonečná posloupnost uzavřených množin
ostře rostoucí vzhledem k inkluzi. Dostáváme spor, neboť podle definice \ref{wqo} části (v) takováto posloupnost není možná. Množina $L$ 
tedy musí být regulární.
 \end{proof}

V předchozím tvrzení jsme dostali zobecnění Nerodovy věty tím, že místo pravé kongruence jsme použili monotónní předuspořádání. V důkazu jsme využili monónnost z prava i zleva,
v případě kongruence nám však stačila pouze monotonie z prava. Jak se ukáže na příkladu, uzavřenost vzhledem k dobrému předuspořádání monotónnímu z prava k regularitě vést nemusít.

Příklad! ($\{ a^n b^m, kde \; n\leq m \}$)

Jednostranná monotonie tedy k regularitě nevede, věta \ref{genMyh} se přesto dá zobecnit. Stačí nalézt dvě dobrá předuspořádání $\leq_1 , \leq_2$, vzhledem k nimž bude jazyk $L$ uzavřený, přičemž $\leq_1$ je monotónní zprava
a $\leq_2$ zleva. 

\begin{veta}
\label{genMyh2}
Nechť $L\subseteq\Sigma^*$.  Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
 dobrému předuspořánaní  $\leq_1$ monotónnímu zprava a  dobrému předuspořánaní  $\leq_2$ monotónnímu zleva.

\end{veta}

K důkazu věty budeme potřebovat několik pojmů. Podobně jako jsme v definici \ref{kontext} definovali na základě kontextu syntaktickou kongruenci, si zadefinujeme \emph{syntaktické monotónní předuspořádání}.

\begin{definice}
Pro $L \subseteq\Sigma^* $ a prvky $x,y \in \Sigma^*$ definujeme relace:
  \[x\leq_L y  \Longleftrightarrow C_L(x) \subseteq C_L(y).\]
  \[x\leq_L^r y  \Longleftrightarrow C_L^r(x) \subseteq C_L^r(y).\]
  \[x\leq_L^l y  \Longleftrightarrow C_L^l(x) \subseteq C_L^l(y).\]
\end{definice}
Podobně jako v případě syntaktické kongruence se snadno ukáže, že syntaktické monotónní předuspořádání (resp. pravé/lévé) je největší monotónní předuspořádání, vzhledem k němuž je jazyk $L$ uzavřený.

\begin{lemma}
\label{monwqo}
 Nechť $L\subseteq\Sigma^*$ a $\leq$ je libovolné pravé (resp. levé) monotónní  předuspořádání na $\Sigma^*$, vzhledem ke kterému je jazyk $L$ uzavřený.  Potom platí, že $\leq \;\subseteq\; \leq_L^r$ (resp. $\leq \;\subseteq\; \leq_L^l$ ). 
\end{lemma}



\begin{proof}
Budeme dokazovat případ pro pravé monotńní předuspořádání.
Nechť  $x, y \in \Sigma^*$ jsou libovolná slova taková, že platí $x \leq y$. Z monotónnie $\leq$ plyne, že $xz \leq yz$ pro libovolné $z \in \Sigma^*$. 
Z uzavřenosti jazyka $L$ vzhledem k $\leq$ potom vyplývá, že $xz \in L \Longrightarrow yz \in L$ a tedy $ C_L^r(x) \subseteq C_L^r(y)$.

\end{proof}

Poslední vlastnost, kterou v důkazu věty \ref{genMyh2} využijeme, je, že se stačí zaměřit právě na předuspořádání $\leq_L^r$ a $\leq_L^l$. Najdeme-li totiž nějaká předuspořádání $\leq_1 , \leq_2$, která splňují podmínky věty \ref{genMyh2}, pak mají tuto vlastnost i $\leq_L^r$, $\leq_L^l$.

\begin{lemma}
\label{subwqo}
Nechť  $\leq_1$ je dobré předuspořádání a  $\leq_2$ je předuspořádání takové, že platí   $\leq_1\subseteq  \leq_2$. Potom je předuspořádání $\leq_2$ dobré.
\end{lemma}
\begin{proof}
K důkazu využijeme definici \ref{wqo}(ii). Pro  $\leq_1$ platí, že v libovolné posloupnosti $\{ x_i \}_{i=1}^\infty $ existují $i,j \in \mathbb{N}, i < j$ taková,
   že $x_i \leq_1 x_j$, tedy i   $x_i \leq_2 x_j$. Předuspořádání  $\leq_2$ je proto také dobré.
\end{proof}

\begin{proof}[Důkaz věty \ref{genMyh2}]
Je-li jazyk $L$ regulární, pak podle věty \ref{genMyh} víme, že je uzavřený vzhledem k dobrému předuspořádání, které je monotónní zprava i zleva. Opačnou implikaci budeme dokazovat sporem.
Nechť tedy $L$ není regulární. Potom podle věty \ref{Myhill-Nerode} má relace $\sim_L^r$ nekonečný index a existuje proto nekonečná posloupnost vzájemně neekvivalentních slov $\{x_i\}_{i=1}^\infty$. Podle předpokladu existují dobrá předuspořádání 
$\leq_1$ resp. $\leq_2$ monotónní zprava resp. zleva, vzhledem k nimž je $L$ uzavřený. Podle lemmat \ref{monwqo} a \ref{subwqo} mají tuto vlastnost také předuspořádání $\leq_L^r$, $\leq_L^l$. Z definice \ref{wqo}(ii) můžeme z posloupnosti $\{x_i\}_{i=1}^\infty$ vybrat podposloupnost $\{y_i\}_{i=1}^\infty$, která bude rostoucí vzhledem k předuspořádání $\leq_L^r$ a to dokonce ostře, neboť jsou $y_i$ vzájemně neekvivalentní v relaci $\sim_L^r$. Platí tedy, že 
$C_L^r(y_i) \subset C_L^r(y_{i+1})$ a posloupnost $\{C_L^r(y_i)\}_{i=1}^\infty$ je tedy ostře rostoucí vzhledem k inkluzi. Je zřejmé, že platí vztah $x\in C_L^r(y) \Longleftrightarrow y\in C_L^l(x) $. Z toho pro libovolná $z_1 \leq_L^l z_2$ plyne, že $z_1 \in C_L^r(y_i) \Longrightarrow y_i \in C_L^l(z_1) \subseteq C_L^l(z_2) \Longrightarrow z_2\in C_L^r(y_i)$.  Posloupnost $\{C_L^r(y_i)\}_{i=1}^\infty$ je pak posloupností uzavřených množin vzhledem k předuspořádání  $\leq_L^l$, která je ostře rostoucí vzhledem k inkluzi. To je ovšem spor s předpokladem, že předuspořádání  $\leq_L^l$ je dobré.
\end{proof}

\section{Nash-Williams}


Užitečným nástrojem pro dokázání, že dané předuspořádání je dobré, poskytuje věta, kterou poprvé dokázal Nash-Williams. K jejímu formulování potřebujeme definovat následující pojem.

\begin{definice}
Nechť $X$ je množina s předuspořádáním $\leq$ a $(x_i)_{i=1}^\infty$ je nekonečná posloupnost prvků množiny $X$. Posloupnost   $(x_i)_{i=1}^\infty$ nazveme \emph{špatnou}, právě když platí
\[  \forall i,j \in \mathbb{N} : i < j  \Longrightarrow x_i \not \leq x_j.\]
\end{definice}

Název \emph{špatná posloupnost} odpovídá tomu, že jsou to práve tyto posloupnosti, které nesmí obsahovat dobře předuspořádaná množina (\ref{wqo}(ii)).

\begin{definice}
Nechť $\leq$ je předuspořádání na množině $X$. Potom předuspořádání $\leq$ nazveme \emph{fundované}, právě když neexistuje nekočná posloupnost  $(x_i)_{i=1}^\infty, x_i \in X$, pro kterou platí $x_{i}>x_{i+1}, i \in \mathbb{N}$.
\end{definice}

Uveďme, že každé dobré předuspořádání je fundované, jak vyplývá z definice \ref{wqo}(iv).

Pro potřeby následující věty je nutné definovat lexikografické předuspořádání na nekonečných posloupnostech. Nechť $X$ je množina předuspořádaná relací $\leq$ a $\sim$ je její jádro. Definujme množinu nekonečných posloupností jako $X^{\omega}$. Potom předuspořádání $\leq$ indukuje předuspořádání na množině $X^{\omega}$ následujícím vztahem:
\[ (x_i)_{i=1}^\infty \leq  (y_i)_{i=1}^\infty \Longleftrightarrow \forall i \in \mathbb{N} : x_i \sim y_i \text{ nebo}\]
\[ \exists n : x_n \leq y_n \wedge \forall i<n : x_i \sim y_i     .\]

\begin{veta}

Nechť $\preceq$ je fundované předuspořádání na množině $X$. Nechť dále $\leq$ je předuspořádání na množině $X$, které není dobré. Potom existuje špatná posloupnost $(x_i)_{i=1}^\infty, x_i \in X$ vzhledem k předuspořádání $\leq$, která je minimální vzhledem k $\preceq$.

\end{veta}

\cleardoublepage

